package com.yangzhe.algorithm.c034;

// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
public class Code01_IntersectionOfTwoLinkedLists_LeetCode {

	// 提交时不要提交这个类
	public static class ListNode {
		public int val;
		public ListNode next;
	}

	/**
	 * 基础的概念：
	 * 1. 两链表如果相交，则之后不可能再分叉
	 * 2. 两链表如果相交，则相交点之后的长度是相同的
	 * 3. 两链表如果相交，则最后的节点一定相同
	 *
	 * 流程：
	 * 1. 分别算两个链表长度
	 * 2. 长度相减
	 * 3. 让长一点的链表先走对应长度差值的步数
	 * 4. 两个链表一起走，第一个相等的节点就是相交的第一个节点
	 * @param h1
	 * @param h2
	 * @return
	 */
	public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {
		if (h1 == null || h2 == null) {
			return null;
		}
		// 1. 获取每个链表长度和尾节点
		NodeTail nodeTail1 = getTailAndLength(h1);
		NodeTail nodeTail2 = getTailAndLength(h2);

		// 如果尾部节点不通，则两个链表一定不相交
		if (nodeTail1.tail != nodeTail2.tail) {
			return null;
		}

		// 2. 获取长的和短的链表头
		ListNode longLengthHead = nodeTail1.length > nodeTail2.length ? nodeTail1.head : nodeTail2.head;
		ListNode shortLengthHead = nodeTail1.length > nodeTail2.length ? nodeTail2.head : nodeTail1.head;

		int diff = Math.abs(nodeTail1.length - nodeTail2.length);

		while (diff != 0) {
			longLengthHead = longLengthHead.next;
            diff--;
        }

		while(longLengthHead != shortLengthHead) {
			longLengthHead = longLengthHead.next;
			shortLengthHead = shortLengthHead.next;
		}

		return longLengthHead;
	}

	/**
	 * 获取链表的长度和尾部节点
	 * @param head 头节点
	 * @return 链表的长度和尾部节点
	 */
	public static NodeTail getTailAndLength(ListNode head) {
		NodeTail nodeTail = new NodeTail();
		nodeTail.head = head;
		while (head != null) {
			nodeTail.length++;
			nodeTail.tail = head;
			head = head.next;
		}

		return nodeTail;
	}

	protected static class NodeTail {
		public int length = 0;

		public ListNode head;
        public ListNode tail;
    }

}
